#include<iostream>
#include<vector>
using namespace std;

class ListNode{
public:
    int val;
    ListNode *next;
};

//面试题08.06.汉诺塔问题
//1.函数头，用到的参数有三个柱子以及转移的个数
void dfs(vector<int>& A,vector<int>& B,vector<int>& C,int n){
    //2.结束条件
    if(n==1){
        C.push_back(A.back());
        A.pop_back();
    }

    //3.函数体，递归实现方式
    //先将A上的n-1个借助C转移到B上
    dfs(A, C, B, n - 1);
    //再将A上的最下面一个转移到C上
    C.push_back(A.back());
    A.pop_back();
    //最后再将B上的n-1个借助A转移到C上
    dfs(B, A, C, n - 1);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C){
    dfs(A, B, C, A.size());
}

//21.合并两个有序链表
//1.函数名，参数用到的是两个链表
ListNode* dfs(ListNode* list1,ListNode* list2){
    //2.结束条件，当其中一个为空时，就返回另一个
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }

    //3.函数体，比较大小
    if(list1->val<list2->val){
        list1->next = dfs(list1->next, list2);
        return list1;
    }
    else{
        list2->next=dfs(list1,list2->next);
        return list2;
    }
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
    return dfs(list1, list2);
}

//206.反转链表
//1.函数名，参数就是节点
ListNode* dfs(ListNode* node){
    //2.结束条件
    //注意要考虑空链表
    if(node==NULL||node->next==NULL){
        return node;
    }

    //3.函数体
    ListNode *newhead = dfs(node->next);
    node->next->next = node;
    node->next = NULL;
    return newhead;
}
ListNode* reverseList(ListNode* head){
    return dfs(head);
}


//24.两两交换链表中的节点
ListNode* dfs1(ListNode* node){
    if(node==NULL||node->next==NULL){
        return node;
    }

    ListNode *cur = dfs1(node->next->next);
    ListNode *newhead = node->next;
    newhead->next = node;
    node->next = cur;
    return newhead;
}
ListNode* swapPairs(ListNode* head){
    return dfs1(head);
}

//50.快速幂
double pow(double x,long long n){
    if(n==0){
        return 1.0;
    }
    double tmp = pow(x, n / 2);
    return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
double myPow(double x, int n){
    //要考虑n为负数的情况
    return n < 0 ? 1.0/pow(x, -(long long)n) : pow(x, (long long)n);
}

int main(){

    return 0;
}